#include <iostream>
#include <stack>

using namespace std;


/**
 * @brief 用双栈实现队列
 * 若弹出栈 stack2 为空，则需要转移 stack1 全部内容到 stack2
 * 虽然转移操作为 O(n)，但是每个元素均摊 O(1) 的额外操作，相当于
 * 每个元素只会被转移一次，因此 push pop 仍皆为 O(1)！
 */
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        // 保证合法
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int res = stack2.top();
        stack2.pop();
        return res;
    }

private:
    stack<int> stack1;  // push into
    stack<int> stack2;  // pop out
};
